package utils

import (
	"container/heap"
	"sync"
)

type EqualInterface interface {
	Equal(other interface{}) bool
}

type Interface interface {
	EqualInterface
	Less(other interface{}) bool
}

type HeapQueue interface {
	Push(x Interface)
	Pop() Interface
	Clean()
	Top() Interface
	Fix(x Interface, i int)
	Remove(i int) Interface
	Len() int
	Contains(i Interface) int
}

type PriorityHeapQueue interface {
	Push(x EqualInterface, priority int)
	Pop() (interface{}, int)
	Clean()
	Len() int
	Top() (interface{}, int)
	Fix(x EqualInterface, priority int)
	Remove(i int) (interface{}, int)
	Contains(i EqualInterface) int
}

type Int int

func (i *Int) Equal(other interface{}) bool {
	return i == other
}
func (i *Int) Value() int {
	return int(*i)
}

type sorter []Interface

// Implement heap.Interface: Push, Pop, Len, Less, Swap
func (s *sorter) Push(x interface{}) {
	*s = append(*s, x.(Interface))
}

func (s *sorter) Pop() interface{} {
	n := len(*s)
	if n > 0 {
		x := (*s)[n-1]
		*s = (*s)[0 : n-1]
		return x
	}
	return nil
}

func (s *sorter) Clean() {
	*s = (*s)[0:0]
}

func (s *sorter) Len() int {
	return len(*s)
}

func (s *sorter) Less(i, j int) bool {
	return (*s)[i].Less((*s)[j])
}

func (s *sorter) Swap(i, j int) {
	(*s)[i], (*s)[j] = (*s)[j], (*s)[i]
}

// Define priority queue struct
type PriorityQueue struct {
	s *sorter
}

func NewQueue() *PriorityQueue {
	q := &PriorityQueue{s: new(sorter)}
	heap.Init(q.s)
	return q
}

func (q *PriorityQueue) Push(x Interface) {
	heap.Push(q.s, x)
}

func (q *PriorityQueue) Pop() Interface {
	if len(*q.s) > 0 {
		return heap.Pop(q.s).(Interface)
	}
	return nil
}

func (q *PriorityQueue) Clean() {
	q.s.Clean()
}

func (q *PriorityQueue) Top() Interface {
	if len(*q.s) > 0 {
		return (*q.s)[0].(Interface)
	}
	return nil
}

func (q *PriorityQueue) Fix(x Interface, i int) {
	heap.Fix(q.s, i)
}

func (q *PriorityQueue) Remove(i int) Interface {
	return heap.Remove(q.s, i).(Interface)
}

func (q *PriorityQueue) Len() int {
	return q.s.Len()
}

func (q *PriorityQueue) Contains(i Interface) int {
	for index, ii := range *q.s {
		if ii.Equal(i) {
			return index
		}
	}
	return -1
}

type SafePriorityQueue struct {
	PriorityQueue
	sync.RWMutex
}

func NewSafeQueue() *SafePriorityQueue {
	q := &SafePriorityQueue{PriorityQueue{s: new(sorter)}, sync.RWMutex{}}
	heap.Init(q.s)
	return q
}
func (q *SafePriorityQueue) Push(x Interface) {
	q.Lock()
	q.PriorityQueue.Push(x)
	q.Unlock()
}

func (q *SafePriorityQueue) Pop() Interface {
	q.Lock()
	v := q.PriorityQueue.Pop()
	q.Unlock()
	return v
}

func (q *SafePriorityQueue) Clean() {
	q.Lock()
	q.PriorityQueue.Clean()
	q.Unlock()
}

func (q *SafePriorityQueue) Top() Interface {
	if len(*q.s) > 0 {
		q.RLock()
		v := (*q.s)[0].(Interface)
		q.RUnlock()
		return v
	}
	return nil
}

func (q *SafePriorityQueue) Fix(x Interface, i int) {
	q.Lock()
	q.PriorityQueue.Fix(x, i)
	q.Unlock()
}

func (q *SafePriorityQueue) Remove(i int) Interface {
	q.Lock()
	v := q.PriorityQueue.Remove(i)
	q.Unlock()
	return v
}

func (q *SafePriorityQueue) Len() int {
	return q.s.Len()
}

func (q *SafePriorityQueue) Contains(i Interface) int {
	for index, ii := range *q.s {
		if ii.Equal(i) {
			return index
		}
	}
	return -1
}

type SmallQueueNode struct {
	Node     EqualInterface
	priority int
}

func (this *SmallQueueNode) Less(other interface{}) bool {
	return this.priority < other.(*SmallQueueNode).priority
}

func (this *SmallQueueNode) Equal(other interface{}) bool {
	return this.Node.Equal(other.(*SmallQueueNode).Node)
}

type BigQueueNode struct {
	Node     EqualInterface
	priority int
}

func (this *BigQueueNode) Less(other interface{}) bool {
	return this.priority > other.(*BigQueueNode).priority
}

func (this *BigQueueNode) Equal(other interface{}) bool {
	return this.Node.Equal(other.(*BigQueueNode).Node)
}

type PriorityNodeQueue struct {
	p *PriorityQueue
}

func NewNodeQueue() *PriorityNodeQueue {
	q := &PriorityNodeQueue{p: NewQueue()}
	return q
}

func (q *PriorityNodeQueue) Push(x EqualInterface, priority int) {
	q.p.Push(&SmallQueueNode{
		Node:     x,
		priority: priority,
	})
}

func (q *PriorityNodeQueue) Pop() (interface{}, int) {
	ii := q.p.Pop().(*SmallQueueNode)
	return ii.Node, ii.priority
}

func (q *PriorityNodeQueue) Clean() {
	q.p.Clean()
}

func (q *PriorityNodeQueue) Top() (interface{}, int) {
	ii := q.p.Top().(*SmallQueueNode)
	return ii.Node, ii.priority
}

func (q *PriorityNodeQueue) Fix(x EqualInterface, priority int) {
	index := q.Contains(x)
	q.p.Fix(&SmallQueueNode{
		Node:     x,
		priority: priority,
	}, index)
}

func (q *PriorityNodeQueue) Remove(i int) (interface{}, int) {
	ii := q.p.Remove(i).(*SmallQueueNode)
	return ii.Node, ii.priority
}

func (q *PriorityNodeQueue) Len() int {
	return q.p.Len()
}

func (q *PriorityNodeQueue) Contains(i EqualInterface) int {
	return q.p.Contains(&SmallQueueNode{
		Node:     i,
		priority: 0,
	})
}

type SafePriorityNodeQueue struct {
	p *SafePriorityQueue
}

func NewSafeNodeQueue() *SafePriorityNodeQueue {
	q := &SafePriorityNodeQueue{p: NewSafeQueue()}
	return q
}

func (q *SafePriorityNodeQueue) Push(x EqualInterface, priority int) {
	q.p.Push(&SmallQueueNode{
		Node:     x,
		priority: priority,
	})
}

func (q *SafePriorityNodeQueue) Pop() (interface{}, int) {
	i := q.p.Pop()
	if i == nil {
		return nil, 0
	}
	ii := i.(*SmallQueueNode)
	return ii.Node, ii.priority
}

func (q *SafePriorityReNodeQueue) Clean() {
	q.p.Clean()
}

func (q *SafePriorityNodeQueue) Top() (interface{}, int) {
	i := q.p.Top()
	if i == nil {
		return nil, 0
	}
	ii := i.(*SmallQueueNode)
	return ii.Node, ii.priority
}

func (q *SafePriorityNodeQueue) Fix(x EqualInterface, priority int) {
	index := q.Contains(x)
	q.p.Fix(&SmallQueueNode{
		Node:     x,
		priority: priority,
	}, index)
}

func (q *SafePriorityNodeQueue) Remove(i int) (interface{}, int) {
	ii := q.p.Remove(i).(*SmallQueueNode)
	return ii.Node, ii.priority
}

func (q *SafePriorityNodeQueue) Len() int {
	return q.p.Len()
}

func (q *SafePriorityNodeQueue) Contains(i EqualInterface) int {
	return q.p.Contains(&SmallQueueNode{
		Node:     i,
		priority: 0,
	})
}

type PriorityReNodeQueue struct {
	p *PriorityQueue
}

func NewReNodeQueue() *PriorityReNodeQueue {
	q := &PriorityReNodeQueue{p: NewQueue()}
	return q
}

func (q *PriorityReNodeQueue) Push(x EqualInterface, priority int) {
	q.p.Push(&BigQueueNode{
		Node:     x,
		priority: priority,
	})
}

func (q *PriorityReNodeQueue) Pop() (interface{}, int) {
	ii := q.p.Pop().(*BigQueueNode)
	return ii.Node, ii.priority
}

func (q *PriorityReNodeQueue) Clean() {
	q.p.Clean()
}

func (q *PriorityReNodeQueue) Top() (interface{}, int) {
	ii := q.p.Top().(*BigQueueNode)
	return ii.Node, ii.priority
}

func (q *PriorityReNodeQueue) Fix(x EqualInterface, priority int) {
	index := q.Contains(x)
	q.p.Fix(&BigQueueNode{
		Node:     x,
		priority: priority,
	}, index)
}

func (q *PriorityReNodeQueue) Remove(i int) (interface{}, int) {
	ii := q.p.Remove(i).(*BigQueueNode)
	return ii.Node, ii.priority
}

func (q *PriorityReNodeQueue) Len() int {
	return q.p.Len()
}

func (q *PriorityReNodeQueue) Contains(i EqualInterface) int {
	return q.p.Contains(&BigQueueNode{
		Node:     i,
		priority: 0,
	})
}

type SafePriorityReNodeQueue struct {
	p *SafePriorityQueue
}

func NewSafeReNodeQueue() *SafePriorityReNodeQueue {
	q := &SafePriorityReNodeQueue{p: NewSafeQueue()}
	return q
}

func (q *SafePriorityReNodeQueue) Push(x EqualInterface, priority int) {
	q.p.Push(&BigQueueNode{
		Node:     x,
		priority: priority,
	})
}

func (q *SafePriorityReNodeQueue) Pop() (interface{}, int) {
	ii := q.p.Pop().(*BigQueueNode)
	return ii.Node, ii.priority
}

func (q *SafePriorityReNodeQueue) Top() (interface{}, int) {
	i := q.p.Top()
	if i == nil {
		return nil, 0
	}
	ii := i.(*BigQueueNode)
	return ii.Node, ii.priority
}

func (q *SafePriorityReNodeQueue) Fix(x EqualInterface, priority int) {
	index := q.Contains(x)
	q.p.Fix(&BigQueueNode{
		Node:     x,
		priority: priority,
	}, index)
}

func (q *SafePriorityReNodeQueue) Remove(i int) (interface{}, int) {
	ii := q.p.Remove(i).(*BigQueueNode)
	return ii.Node, ii.priority
}

func (q *SafePriorityReNodeQueue) Len() int {
	return q.p.Len()
}

func (q *SafePriorityReNodeQueue) Contains(i EqualInterface) int {
	return q.p.Contains(&BigQueueNode{
		Node:     i,
		priority: 0,
	})
}
